import java.util.*;

public class Qus100 {
    class Solution15 {
        public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> list = new ArrayList<>();
            for (int i = 0; i < nums.length - 2; i++) {
                if (nums[i] > 0) {
                    return list;
                }
                int l = i + 1, r = nums.length - 1;
                if (i > 0 && nums[i - 1] == nums[i])
                    continue;
                while (l < r) {
                    int sum = nums[i] + nums[l] + nums[r];
                    if (sum > 0) {
                        r--;
                    } else if (sum < 0) {
                        l++;
                    } else {
                        List<Integer> sublist = new ArrayList<>();
                        sublist.add(nums[i]);
                        sublist.add(nums[l]);
                        sublist.add(nums[r]);
                        list.add(sublist);
                        while (l < r && nums[r] == nums[r - 1]) r--;
                        while (l < r && nums[l] == nums[l + 1]) l++;
                        r--;
                        l++;
                    }
                }
            }
            return list;
        }
    }

    class Solution3 {
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> list = new ArrayList<>();
            if (p.length() > s.length())
                return list;
            char[] sp = p.toCharArray();
            char[] ss = s.toCharArray();
            int[] sp1 = new int[26];
            int[] ss1 = new int[26];
            for (int i = 0; i < p.length(); i++) {
                sp1[sp[i] - 'a']++;
                ss1[ss[i] - 'a']++;
            }
            for (int i = 0; i < s.length() - p.length() + 1; i++) {
                if (Arrays.equals(sp1, ss1)) {
                    list.add(i);
                }
                if (i + p.length() < s.length()) {
                    ss1[ss[i] - 'a']--;
                    ss1[ss[i + p.length()] - 'a']++;
                }
            }
            return list;
        }
    }

    class Solution560 {
        public int subarraySum1(int[] nums, int k) {
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                int sum = 0;
                for (int j = i; j < nums.length; j++) {
                    sum = sum + nums[j];
                    if (sum == k) {
                        count++;
                    }
                }
            }
            return count;
        }

        public int subarraySum(int[] nums, int k) {
            int count = 0;
            Map<Integer, Integer> map = new HashMap<>();
            map.put(0, 1);
            int sum = 0;
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
                if (map.containsKey(sum - k)) {
                    count += map.get(sum - k);
                }
                if (!map.containsKey(sum)) {
                    map.put(sum, map.getOrDefault(sum, 0) + 1);
                }
            }
            return count;
        }
    }

    class Solution239 {
        public int[] maxSlidingWindow1(int[] nums, int k) {
            int n = nums.length;
            int[] res = new int[n - k + 1];
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
            for (int i = 0; i < n; i++) {
                pq.offer(new int[]{nums[i], i});
                while (pq.peek()[1] < i - k + 1) {
                    pq.poll();
                }
                if (i >= k - 1) {
                    res[i - k + 1] = pq.peek()[0];
                }
            }
            return res;
        }

        public int[] maxSlidingWindow01(int[] nums, int k) {
            int n = nums.length;
            int[] res = new int[n - k + 1];
            Deque<int[]> deque = new LinkedList<>();
            for (int i = 0; i < n; i++) {
                while (!deque.isEmpty() && deque.peekLast()[0] < nums[i]) {
                    deque.pollLast();
                }
                if (!deque.isEmpty() && deque.peekFirst()[1] <= i - k) {
                    deque.pollFirst();
                }
                deque.offerLast(new int[]{nums[i], i});
                if (deque.peekLast()[1] >= k - 1) {
                    res[i - k + 1] = deque.peekFirst()[0];
                }
            }
            return res;
        }

        public int[] maxSlidingWindo2(int[] nums, int k) {
            if (nums == null || k == 0) return new int[0];

            int n = nums.length;
            int[] result = new int[n - k + 1];

            // 大根堆，存储 Pair<值, 下标>
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);

            for (int i = 0; i < n; i++) {
                // 把当前元素加入堆中
                pq.offer(new int[]{nums[i], i});

                // 如果堆顶元素不在窗口范围内，移除它
                while (pq.peek()[1] <= i - k) {
                    pq.poll();
                }

                // 当窗口形成后，把堆顶元素（最大值）加入结果
                if (i >= k - 1) {
                    result[i - k + 1] = pq.peek()[0];
                }
            }

            return result;
        }

        public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums.length == 0 || k == 0) return new int[0];

            int n = nums.length;
            int[] result = new int[n - k + 1];
            Deque<Integer> deque = new LinkedList<>(); // 保存的是下标

            for (int i = 0; i < n; i++) {
                // 移除窗口外的下标
                if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                    deque.pollFirst();
                }

                // 弹出所有比当前值小的下标（保持递减）
                while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                    deque.pollLast();
                }

                deque.offerLast(i); // 加入当前下标

                // 当窗口形成时，记录最大值
                if (i >= k - 1) {
                    result[i - k + 1] = nums[deque.peekFirst()];
                }
            }

            return result;
        }
    }

    class Solution76 {
        public String minWindow(String s, String t) {
            Map<Character, Integer> maps = new HashMap<>();
            Map<Character, Integer> mapt = new HashMap<>();
            int window = 0;
            for (int i = 0; i < t.length(); i++) {
                mapt.put(t.charAt(i), mapt.getOrDefault(t.charAt(i), 0) + 1);
            }
            int size = mapt.size();
            int l = 0;
            int min = Integer.MAX_VALUE;
            int right = 0;
            int left = 0;
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if (mapt.containsKey(ch)) {
                    maps.put(ch, maps.getOrDefault(ch, 0) + 1);
                    if (mapt.get(ch).intValue() == maps.get(ch).intValue()) {
                        window++;
                    }
                }

                while (window == size) {
                    if (i - l + 1 < min) {
                        left = l;
                        right = i + 1;
                        min = right - left;
                    }
                    char sh = s.charAt(l);
                    if (mapt.containsKey(sh)) {
                        maps.put(sh, maps.get(sh) - 1);
                        if (mapt.get(sh) > maps.get(sh)) {
                            window--;
                        }
                    }
                    l++;
                }
            }
            return min == Integer.MAX_VALUE ? "" : s.substring(left, right);
        }
    }

    class Solution56 {
        public int[][] merge1(int[][] intervals) {
            List<int[]> list = new ArrayList<>();
            Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
            for (int i = 0; i < intervals.length; i++) {
                if (i == 0) {
                    list.add(new int[]{intervals[i][0], intervals[i][1]});
                }
                int l = intervals[i][0];
                if (l <= list.get(list.size() - 1)[1]) {
                    int l1 = list.get(list.size() - 1)[0];
                    int r1 = Math.max(list.get(list.size() - 1)[1], intervals[i][1]);
                    list.set(list.size() - 1, new int[]{l1, r1});
                } else {
                    list.add(new int[]{intervals[i][0], intervals[i][1]});
                }
            }
            return list.toArray(new int[0][]);

        }

        public int[][] merge(int[][] intervals) {
            if (intervals.length == 0) return new int[0][];

            List<int[]> list = new ArrayList<>();

            // 先按照起始位置排序
            Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

            // 把第一个区间先加进去
            list.add(new int[]{intervals[0][0], intervals[0][1]});

            // 从第二个开始遍历
            for (int i = 1; i < intervals.length; i++) {
                int[] last = list.get(list.size() - 1);  // 当前已合并区间的最后一个
                int[] current = intervals[i];

                if (current[0] <= last[1]) {
                    // 有重叠，合并
                    last[1] = Math.max(last[1], current[1]);
                } else {
                    // 无重叠，直接添加新区间
                    list.add(new int[]{current[0], current[1]});
                }
            }

            return list.toArray(new int[0][]);
        }
    }

    class Solution189 {
        public void rotate(int[] nums, int k) {
            int n = nums.length;
            if (k % n == 0) {
                return;
            }
            int cur;
            int count = 0;
            int tmp = nums[0];
            int i = 0;
            int il = 0;
            while (count < n) {
                cur = tmp;
                tmp = nums[(i + k) % n];
                nums[(i + k) % n] = cur;
                i = (i + k) % n;
                if (i == il) {
                    i++;
                    il++;
                    tmp = nums[i];
                }
                count++;
            }
        }
    }

    class Solution35 {
        public int searchInsert(int[] nums, int target) {
            if (target < nums[0]) {
                return 0;
            }
            if (target > nums[nums.length - 1]) {
                return nums.length;
            }
            int mid = 0;
            int l = 0;
            int r = nums.length - 1;
            int res = 0;
            while (l < r) {
                mid = (l + r) / 2;
                if (nums[mid] == target) {
                    return mid;
                } else if (nums[mid] > target) {
                    r = mid - 1;

                } else {
                    l = mid + 1;
                }
            }
            if (nums[l] < target) {
                res = l + 1;
            } else {
                res = l;
            }
            return res;
        }
    }

    class Solution215 {
        public int findKthLargest1(int[] nums, int k) {
            Deque<Integer> dq = new LinkedList<>();
            Deque<Integer> predq = new LinkedList<>();
            for (int i = 0; i < nums.length; i++) {
                if (dq.isEmpty()) {
                    dq.offerFirst(nums[0]);
                    continue;
                }
                if (dq.peekFirst() <= nums[i]) {
                    dq.offerFirst(nums[i]);
                    while (dq.size() > k) {
                        dq.pollLast();
                    }
                } else {
                    if (dq.peekLast() < nums[i]) {
                        while (!dq.isEmpty() && dq.peekLast() < nums[i]) {
                            predq.offerLast(dq.peekLast());
                            dq.pollLast();
                        }
                        dq.offerLast(nums[i]);
                        while (!predq.isEmpty()) {
                            if (dq.size() < k)
                                dq.offerLast(predq.peekLast());
                            predq.pollLast();
                        }
                    } else if (dq.size() < k) {
                        dq.offerLast(nums[i]);
                    }
                }
            }
            while (k > 1) {
                dq.pollFirst();
                k--;
            }
            return dq.peekFirst();
        }

        public int findKthLargest(int[] nums, int k) {
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>(((a, b) -> b - a));
            for (int num : nums) {
                maxHeap.offer(num);
            }
            while (k > 1) {
                maxHeap.poll();
                k--;// 移除最大的，保留 k 个最大的
            }
            return maxHeap.peek(); // 堆顶是第 k 大
        }
    }

    class Solution121 {
        public int maxProfit(int[] prices) {
            int n = prices.length;
            if (n <= 1) {
                return 0;
            }
            int min = prices[0];
            int max = prices[0];
            int res = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] < min) {
                    min = prices[i];
                    max = prices[i];
                }
                if (prices[i] > max) {
                    max = prices[i];
                    if (max - min > res) {
                        res = max - min;
                    }
                }

            }
            return res;
        }
    }

    class Solution118 {
        public List<List<Integer>> generate(int numRows) {
            List<List<Integer>> res = new ArrayList<>();

            for (int i = 0; i < numRows; i++) {
                List<Integer> ans = new ArrayList<>();
                for (int j = 0; j < i + 1; j++) {
                    if (j == 0 || j == i) {
                        ans.add(1);
                    } else {
                        ans.add(res.get(i - 1).get(j) + res.get(i - 1).get(j - 1));
                    }
                }
                res.add(ans);
            }

            return res;
        }
    }

    class Solution198 {
        public int rob(int[] nums) {
            int n = nums.length;
            if (n == 1) {
                return nums[0];
            }
            if (n == 2) {
                return Math.max(nums[0], nums[1]);
            }
            int[] res = new int[n];
            res[0] = nums[0];
            res[1] = Math.max(res[0], nums[1]);
            for (int i = 2; i < n; i++) {
                res[i] = Math.max(res[i - 1], res[i - 2] + nums[i]);
            }
            return res[n - 1];
        }
    }

    class Solution322 {
        public int coinChange(int[] coins, int amount) {
            if (amount == 0) {
                return 0;
            }
            int[] res = new int[amount + 1];
            Arrays.fill(res, Integer.MAX_VALUE);
            res[0] = 0;
            for (int i = 0; i < coins.length; i++) {
                if (coins[i] > amount) continue;
                for (int j = coins[i]; j <= amount; j++) {
                    if (res[j - coins[i]] != Integer.MAX_VALUE)
                        res[j] = Math.min(res[j - coins[i]] + 1, res[j]);
                }
            }
            return res[amount] == Integer.MAX_VALUE ? -1 : res[amount];
        }
    }

    class Solution279 {
        public int numSquares(int n) {
            int[] res = new int[n + 1];
            Arrays.fill(res, n);
            res[0] = 0;
            for (int i = 1; i <= Math.sqrt(n); i++) {
                for (int j = i * i; j <= n; j++) {
                    res[j] = Math.min(res[j - i * i] + 1, res[j]);
                }
            }
            return res[n + 1];
        }
    }

    class Solution139 {
        public boolean wordBreak(String s, List<String> wordDict) {
            Set<String> stringSet = new HashSet<>(wordDict);
            boolean[] dp = new boolean[s.length() + 1];
            dp[0] = true;

            for (int i = 1; i <= s.length(); i++) {
                for (int j = i - 1; j >= 0; j--) {
                    if (dp[j] && stringSet.contains(s.substring(j, i))) {
                        dp[i] = true;
                        break; // 找到一个即可，不用继续
                    }
                }
            }
            return dp[s.length()];
        }
    }

    class Solution300 {
        public int lengthOfLIS(int[] nums) {
            int n = nums.length;
            int[] res = new int[n];
            Arrays.fill(res, 1);
            int ans = 1;
            for (int i = 1; i < n; i++) {
                for (int j = i - 1; j >= 0; j--) {
                    if (nums[i] > nums[j]) {
                        res[i] = Math.max(res[j] + 1, res[i]);
                    }
                }
                ans = Math.max(ans, res[i]);
            }
            return ans;
        }
    }

    class Solution64 {
        public int minPathSum(int[][] grid) {
            int h = grid.length;
            int w = grid[0].length;
            int[][] res = new int[h][w];
//            Arrays.fill(res,Integer.MAX_VALUE);
            res[0][0] = grid[0][0];
            for (int i = 1; i < w; i++) {
                res[0][i] = res[0][i - 1] + grid[0][i];
            }
            for (int i = 1; i < h; i++) {
                res[i][0] = res[i - 1][0] + grid[i][0];
            }
            for (int i = 1; i < h; i++) {
                for (int j = 1; j < w; j++) {
                    res[i][j] = Math.min(res[i - 1][j], res[i][j - 1]) + grid[i][j];
                }
            }
            return res[h - 1][w - 1];
        }
    }

    class Solution74 {
        public boolean searchMatrix(int[][] matrix, int target) {
            int h = matrix.length;
            int w = matrix[0].length;

            // 先在第一列找行
            int top = 0, bottom = h - 1;
            while (top <= bottom) {
                int mid = (top + bottom) / 2;
                if (matrix[mid][0] == target) {
                    return true;
                } else if (matrix[mid][0] < target) {
                    top = mid + 1;
                } else {
                    bottom = mid - 1;
                }
            }

            // bottom 现在是可能所在的行
            if (bottom < 0) return false;
            int row = bottom;

            // 在这一行二分查找
            int left = 0, right = w - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (matrix[row][mid] == target) {
                    return true;
                } else if (matrix[row][mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

            return false;
        }
    }

    class Solution34 {
        public int[] searchRange(int[] nums, int target) {
            int l = 0;
            int r = nums.length - 1;
            int find = 0;
            int pos = 0;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (nums[mid] == target) {
                    find = 1;
                    pos = mid;
                    break;
                } else if (nums[mid] < target) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            if (find == 0) {
                return new int[]{-1, -1};
            } else {
                int resl = pos;
                int resr = pos;
                while (resl >= 0 && nums[resl] == target) {
                    resl--;
                }
                while (resr <= r && nums[resr] == target) {
                    resr++;
                }
                return new int[]{resl + 1, resr - 1};
            }
        }
    }

    class Solution46 {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();

        public List<List<Integer>> permute(int[] nums) {

            for (int i = 0; i < nums.length; i++) {
                int[] used = new int[nums.length];
                used[i] = 1;
                list.add(nums[i]);
                back(nums, used);
                list.remove(0);
                used[i] = 0;
            }
            return res;
        }

        private void back(int[] nums, int[] used) {
            if (list.size() == nums.length) {
                res.add(new ArrayList<>(list));
                return;
            }
            for (int i = 0; i < nums.length; i++) {
                if (used[i] == 1)
                    continue;
                list.add(nums[i]);
                used[i] = 1;
                back(nums, used);
                list.remove(list.size() - 1);
                used[i] = 0;
            }
        }
    }

    class Solution78 {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();

        public List<List<Integer>> subsets(int[] nums) {
            res.add(new ArrayList<>());
            for (int i = 0; i < nums.length; i++) {
                list.add(nums[i]);
                res.add(new ArrayList<>(list));
                back(i, nums);
                list.remove(list.size() - 1);
            }
            return res;
        }

        private void back(int i, int[] nums) {
            if (i >= nums.length) {
                return;
            }
            for (int j = i + 1; j < nums.length; j++) {
                list.add(nums[j]);
                res.add(new ArrayList<>(list));
                back(j, nums);
                list.remove(list.size() - 1);
            }
        }
    }

    class Solution17 {
        List<String> res = new ArrayList<>();
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};

        public List<String> letterCombinations(String digits) {

            if (digits.isEmpty())
                return new ArrayList<>();
            char[] ch = phoneMap.get(digits.charAt(0)).toCharArray();
            for (int i = 0; i < ch.length; i++) {
                StringBuffer s = new StringBuffer();
                s.append(ch[i]);
                back(1, digits, s);
            }

            return res;
        }

        private void back(int i, String digits, StringBuffer s) {
            if (i >=digits.length()) {
                res.add(s.toString());
                return ;
            }

            char[] ch = phoneMap.get(digits.charAt(i)).toCharArray();
            for (int j = 0; j < ch.length; j++) {
                s.append(ch[j]);
                back(i + 1, digits, s);
                s.deleteCharAt(s.length()-1);
            }
        }
    }

    class Solution20 {
        public boolean isValid(String s) {
            Deque<Character> deque = new LinkedList<>();
            for(int i=0;i<s.length();i++){
                char c = s.charAt(i);
                if(deque.isEmpty()){
                    deque.offerLast(c);
                }else {
                    if(c==')'&&deque.peekLast()=='('){
                            deque.pollLast();
                    }else if(c==']'&&deque.peekLast()=='['){
                            deque.pollLast();
                    }else if(c=='}'&&deque.peekLast()=='{') {
                            deque.pollLast();
                    }else {
                        deque.offerLast(c);
                    }
                }
            }
            return deque.isEmpty();
        }
    }

    class Solution45 {
        public int jump1(int[] nums) {
            int[] res = new int[nums.length];
            Arrays.fill(res, Integer.MAX_VALUE);
            res[0] = 0;
            for (int i = 0; i < nums.length; i++) {
                for (int j = i + 1; j < (nums[i] + i + 1 > nums.length ? nums.length : nums[i] + i + 1); j++) {
                    res[j] = Math.min(res[i] + 1, res[j]);
                }
            }
            return res[nums.length - 1];
        }
        public int jump(int[] nums) {
            if(nums.length==1){
                return 0;
            }
            int res = 0;
            int cover=0;
            int max= 0;
            for(int i=0;i<nums.length;i++){
                max = Math.max(max,i+nums[i]);
                if(i==cover){
                    res++;
                    cover = max;
                }
                if(cover>= nums.length-1){
                    break;
                }
            }
            return res;
        }
    }

    class Solution763 {
        public List<Integer> partitionLabels(String s) {
            List<Integer> res = new ArrayList<>();
            Map<Character,Integer> map = new HashMap<>();
            for(int i = 0;i<s.length();i++){
                char c = s.charAt(i);
                map.put(c,i);
            }
            int max=0;
            int last=0;
            for(int i = 0;i<s.length();i++){
                char c = s.charAt(i);
                max = Math.max(max,map.get(c));
                if(max==i){
                    last=i+1-last;
                    res.add(last);
                    last = i+1;

                }
            }
            return res;
        }
        public List<Integer> partitionLabels1(String s) {
            List<Integer> res = new ArrayList<>();
            int[] map = new int[124];   // 用ASCII码范围
            char[] ch = s.toCharArray();
            for (int i = 0; i < ch.length; i++) {
                map[ch[i]] = i;         // 直接用字符ASCII做索引
            }
            int max = 0;
            int last = 0;
            for (int i = 0; i < ch.length; i++) {
                max = Math.max(max, map[ch[i]]);
                if (max == i) {
                    last = i + 1 - last;
                    res.add(last);
                    last = i + 1;
                }
            }
            return res;
        }
    }

    class Solution39 {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            int sum=0;
            Arrays.sort(candidates);
            back(candidates,target,sum,0);
            return res;
        }

        private void back(int[] candidates, int target, int sum,int index) {
            if(sum==target){
                res.add(new ArrayList<>(list));
                return;
            }if(sum>target){
                return;
            }
            for (int i = index;i<candidates.length;i++) {
                sum = sum + candidates[i];
                if(sum>target){
                    continue;
                }
                list.add(candidates[i]);
                back(candidates, target, sum,i);
                sum = sum - candidates[i];
                list.remove(list.size() - 1);
            }
        }
    }
}





